// https://leetcode.cn/problems/longest-common-prefix/

// 题干：编写一个函数来查找字符串数组中的最长公共前缀。
//      如果不存在公共前缀，返回空字符串 ""。

// 示例：输入：strs = ["flower","flow","flight"]
//      输出："fl"

// 碎语：O(N*M)的方法好想，所有字符串统一位置进行比较

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 1) return strs[0]; // 特殊情况

        string res;

        for (int i = 0 ; i < strs[0].size() ; i++){
            char ch = strs[0][i];

            for (int j = 1 ; j < strs.size() ; j++){
                if (i >= strs[j].size() || strs[j][i] != ch) return res;
            }
            res.push_back(ch);
        }

        return res;
    }
};

int main()
{
    Solution sol;
    vector<string> strs = {"flower","flow","flight"};

    string index = sol.longestCommonPrefix(strs);
    cout << index << endl;

    return 0;
}